// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-12 15:15
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Intervalsummation;

/**
 * 预构建线段树可以判断区间是否重合，使用动态开点线段树实现线段树区域外区间的正确返回
 */
public class Solution {
    Node root = new Node(1,50);

    public boolean isCovered(int[][] ranges, int left, int right) {
        for (int[] range : ranges) {
            update(range[0], range[1]);
        }
        return query(left, right);
    }

    private boolean query(int left, int right) {
        return query(root, left, right);
    }

    private boolean query(Node root, int left, int right) {
        if (root == null) {
            return false;
        }
        if (root.start == left && root.end == right) {
            return true;
        }
        int mid = root.start + ((root.end - root.start) >> 1);
        if (mid >= right) {
            return query(root.left, left, right);
        } else if (mid < left) {
            return query(root.right, left, right);
        } else {
            boolean lb = query(root.left, left, mid);
            boolean rb = query(root.right, mid + 1, right);
            return lb && rb;
        }

    }

    private void update(int left, int right) {
        if (left > right) {
            throw new IllegalArgumentException("left is bigger than right!");
        }
        update(root, left, right);
    }

    private void update(Node root, int left, int right) {
        if (root == null) {
            this.root = new Node(left, right);
            return;
        }
        int mid = root.start + ((root.end - root.start) >> 1);
        if (mid >= right) {
            update(root.left, left, right);
        } else if (mid < left) {
            update(root.right, left, right);
        } else {
            update(root.left, left, mid);
            update(root.right, mid + 1, right);
        }
        pushUp(root);
    }

    private void pushUp(Node root) {
        root.v = root.left.v + root.right.v;
    }

    class Node {
        int start, end, v;
        Node left, right;

        public Node(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) {
        //int[][] ranges = {{1, 2}};
        int[][] ranges = {{1, 2}, {3, 4}, {5, 6}};
        //int[][] ranges = {{1, 10}, {10, 20}};
        int left = 2, right = 5;
        Solution ic = new Solution();
        System.out.println(ic.isCovered(ranges, left, right));
    }


}
